package first

/*
	输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

	要求时间复杂度为O(n)。

	示例1:

	输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
	输出: 6
	解释:连续子数组[4,-1,2,1] 的和最大，为6。

	提示：

	1 <=arr.length <= 10^5
	-100 <= arr[i] <= 100

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func maxSubArray(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	dp := make([]int, len(nums)) //dp[i]表示以i结尾的连续子数组的最大和(注意：该和必须包含末尾元素nums[i])
	for i := 0; i < len(dp); i++ {
		dp[i] = nums[i]
	}
	maxs := dp[0]
	for i := 1; i < len(nums); i++ {
		if dp[i-1]+nums[i] > nums[i] { // 如果dp[i-1]+nums[i]<nums[i]、则说明dp[i-1]为负数、所以重新选取当前元素为子数组的起点
			dp[i] = nums[i] + dp[i-1]
		}
		maxs = max(maxs, dp[i])
	}
	return maxs
}
